#include "stand.h"

extern int a[];

//递归，栈，一层层执行
void merge_sort(int *a,int ac) 
{
	int i,j,k;
	int ac1,ac2;
	int *ah1,*ah2;
	int *container;

	/*base case*/
	if (ac <= 1) return;

	/*split the array into two*/
	ac1 = ac/2;
	ac2 = ac - ac1;//帅气，防止ac为奇数
	ah1 = a + 0; //帅气，ah1,ah2分别指向数组的两部分
	ah2 = a + ac1;
	/*recusion*/
	merge_sort(ah1,ac1);
	merge_sort(ah2,ac2);

	/*merge*/
	i = 0;
	j = 0;
	k = 0;
	
	container = malloc(sizeof(int)*ac);//为一个int指针申请和原数组相同的内存空间
	while (i < ac1 && j < ac2) {
		if (ah1[i] <= ah2[j]) {
			container[k++] = ah1[i++];// 即用于赋值，又可以++。帅气
		} else {
			container[k++] = ah2[j++];
		}
	}

	while (i < ac1) {
		container[k++] = ah1[i++];
	}

	while (j < ac2) {
		container[k++] = ah2[j++];
	}
	/* 上面的两个循环的作用是？？？   猜测是为了上面while循环中漏掉的内容*/

	for (i=0; i<ac ;i++) {
		a[i] = container[i];
	}

	free(container);


}

int main()
{

	int ac = ARRLEN(a,int);
	merge_sort(a,ac);
	print_arr(a,ac);

}
